Computational investigations of maximum flow algorithms
Identifieur interne : 002952 ( Main/Exploration ); précédent : 002951; suivant : 002953Computational investigations of maximum flow algorithms
Auteurs : Ravindra K. Ahuja [Inde] ; Murali Kodialam [États-Unis] ; Ajay K. Mishra [États-Unis] ; James B. Orlin [États-Unis]Source :
- European Journal of Operational Research [ 0377-2217 ] ; 1996.
Abstract
The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path algorithm, and the capacity-scaling algorithm. The preflow-push algorithms tested by us include Karzanov's algorithm, three implementations of Goldberg-Tarjan's algorithm, and three versions of Ahuja-Orlin-Tarjan's excess-scaling algorithms. Among many findings, our study concludes that the preflow-push algorithms are substantially faster than other classes of algorithms, and the highest-label preflow-push algorithm is the fastest maximum flow algorithm for which the growth rate in the computational time is O(n1.5) on four out of five of our problem classes. Further, in contrast to the results of the worst-case analysis of maximum flow algorithms, our study finds that the time to perform relabel operations (or constructing the layered networks) takes at least as much computation time as that taken by augmentations and/or pushes.
Url:
DOI: 10.1016/S0377-2217(96)00269-X
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001632
- to stream Istex, to step Curation: 001632
- to stream Istex, to step Checkpoint: 000D70
- to stream Main, to step Merge: 002A72
- to stream Main, to step Curation: 002952
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Computational investigations of maximum flow algorithms</title>
<author><name sortKey="Ahuja, Ravindra K" sort="Ahuja, Ravindra K" uniqKey="Ahuja R" first="Ravindra K." last="Ahuja">Ravindra K. Ahuja</name>
</author>
<author><name sortKey="Kodialam, Murali" sort="Kodialam, Murali" uniqKey="Kodialam M" first="Murali" last="Kodialam">Murali Kodialam</name>
</author>
<author><name sortKey="Mishra, Ajay K" sort="Mishra, Ajay K" uniqKey="Mishra A" first="Ajay K." last="Mishra">Ajay K. Mishra</name>
</author>
<author><name sortKey="Orlin, James B" sort="Orlin, James B" uniqKey="Orlin J" first="James B." last="Orlin">James B. Orlin</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:C70C8062F29D1B7A2EB5510574001C9AB0943E71</idno>
<date when="1997" year="1997">1997</date>
<idno type="doi">10.1016/S0377-2217(96)00269-X</idno>
<idno type="url">https://api.istex.fr/document/C70C8062F29D1B7A2EB5510574001C9AB0943E71/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001632</idno>
<idno type="wicri:Area/Istex/Curation">001632</idno>
<idno type="wicri:Area/Istex/Checkpoint">000D70</idno>
<idno type="wicri:doubleKey">0377-2217:1997:Ahuja R:computational:investigations:of</idno>
<idno type="wicri:Area/Main/Merge">002A72</idno>
<idno type="wicri:Area/Main/Curation">002952</idno>
<idno type="wicri:Area/Main/Exploration">002952</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a">Computational investigations of maximum flow algorithms</title>
<author><name sortKey="Ahuja, Ravindra K" sort="Ahuja, Ravindra K" uniqKey="Ahuja R" first="Ravindra K." last="Ahuja">Ravindra K. Ahuja</name>
<affiliation wicri:level="1"><country xml:lang="fr">Inde</country>
<wicri:regionArea>Department of Industrial and Management Engineering, Indian Institute of Technology, Kanpur, 208 016</wicri:regionArea>
<wicri:noRegion>208 016</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Kodialam, Murali" sort="Kodialam, Murali" uniqKey="Kodialam M" first="Murali" last="Kodialam">Murali Kodialam</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>AT&T Bell Laboratories, Holmdel, NJ 07733</wicri:regionArea>
<placeName><region type="state">New Jersey</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Mishra, Ajay K" sort="Mishra, Ajay K" uniqKey="Mishra A" first="Ajay K." last="Mishra">Ajay K. Mishra</name>
<affiliation wicri:level="4"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>KATZ Graduate School of Business, University of Pittsburgh, Pittsburgh, PA 15260</wicri:regionArea>
<placeName><region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Orlin, James B" sort="Orlin, James B" uniqKey="Orlin J" first="James B." last="Orlin">James B. Orlin</name>
<affiliation><wicri:noCountry code="no comma">Corresponding author.</wicri:noCountry>
</affiliation>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02139</wicri:regionArea>
<placeName><region type="state">Massachusetts</region>
</placeName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">European Journal of Operational Research</title>
<title level="j" type="abbrev">EOR</title>
<idno type="ISSN">0377-2217</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1996">1996</date>
<biblScope unit="volume">97</biblScope>
<biblScope unit="issue">3</biblScope>
<biblScope unit="page" from="509">509</biblScope>
<biblScope unit="page" to="542">542</biblScope>
</imprint>
<idno type="ISSN">0377-2217</idno>
</series>
<idno type="istex">C70C8062F29D1B7A2EB5510574001C9AB0943E71</idno>
<idno type="DOI">10.1016/S0377-2217(96)00269-X</idno>
<idno type="PII">S0377-2217(96)00269-X</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0377-2217</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path algorithm, and the capacity-scaling algorithm. The preflow-push algorithms tested by us include Karzanov's algorithm, three implementations of Goldberg-Tarjan's algorithm, and three versions of Ahuja-Orlin-Tarjan's excess-scaling algorithms. Among many findings, our study concludes that the preflow-push algorithms are substantially faster than other classes of algorithms, and the highest-label preflow-push algorithm is the fastest maximum flow algorithm for which the growth rate in the computational time is O(n1.5) on four out of five of our problem classes. Further, in contrast to the results of the worst-case analysis of maximum flow algorithms, our study finds that the time to perform relabel operations (or constructing the layered networks) takes at least as much computation time as that taken by augmentations and/or pushes.</div>
</front>
</TEI>
<affiliations><list><country><li>Inde</li>
<li>États-Unis</li>
</country>
<region><li>Massachusetts</li>
<li>New Jersey</li>
<li>Pennsylvanie</li>
</region>
<orgName><li>Université de Pittsburgh</li>
</orgName>
</list>
<tree><country name="Inde"><noRegion><name sortKey="Ahuja, Ravindra K" sort="Ahuja, Ravindra K" uniqKey="Ahuja R" first="Ravindra K." last="Ahuja">Ravindra K. Ahuja</name>
</noRegion>
</country>
<country name="États-Unis"><region name="New Jersey"><name sortKey="Kodialam, Murali" sort="Kodialam, Murali" uniqKey="Kodialam M" first="Murali" last="Kodialam">Murali Kodialam</name>
</region>
<name sortKey="Mishra, Ajay K" sort="Mishra, Ajay K" uniqKey="Mishra A" first="Ajay K." last="Mishra">Ajay K. Mishra</name>
<name sortKey="Orlin, James B" sort="Orlin, James B" uniqKey="Orlin J" first="James B." last="Orlin">James B. Orlin</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/OperaV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002952 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002952 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Musique |area= OperaV1 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:C70C8062F29D1B7A2EB5510574001C9AB0943E71 |texte= Computational investigations of maximum flow algorithms }}
This area was generated with Dilib version V0.6.21. |